package datastructure.priorityqueue;


/**
 * 基于大顶堆实现优先级队列
 *
 * @author 杨 强
 * @package datastructure.priorityqueue
 * @createTime 2023-03-18 20:59
 */
public class MaxHeapPriorityQueue<E extends Priority> implements Queue<E> {
    public static void main(String[] args) {
        Element element1 = new Element(1, 1);
        Element element2 = new Element(2, 2);
        Element element3 = new Element(3, 3);
        Element element4 = new Element(4, 4);
        Element element5 = new Element(5, 5);

        MaxHeapPriorityQueue<Element> queue = new MaxHeapPriorityQueue(5);

        queue.offer(element1);
        queue.offer(element2);
        queue.offer(element3);
        queue.offer(element4);
        queue.offer(element5);

        System.out.println("应该是5, 实际是: " + queue.poll().data);
        System.out.println("应该是4, 实际是: " + queue.poll().data);
        System.out.println("应该是3, 实际是: " + queue.poll().data);
        System.out.println("应该是2, 实际是: " + queue.poll().data);
        System.out.println("应该是1, 实际是: " + queue.poll().data);
    }

    @Override
    public boolean offer(E value) {
        // 判满
        if (isFull()){
            return false;
        }
        // 数组待插入数据的下标就是最后一个下标, 也就是size, 加入后再加一.
        int child = size++;
        // 得到插入数据下标的父节点, 这里可以看堆的求父节点规律
        int parent = (child - 1) / 2;
        // 0不用进行比较, 子节点和父节点进行比较,父节点在和父节点的父节点比较,大的就放最上面
        while (child > 0 && value.priority() > array[parent].priority()){
            // 父节点比子节点大,值交换
            array[child] = array[parent];
            // 下标交换
            child = parent;
            // 继续比较上一个
            parent = (child - 1) / 2;
        }
        // 插入值
        array[child] = value;
        return true;
    }

    @Override
    public E poll() {
        // 判空
        if (isEmpty()){
            return null;
        }
        // 把数组0下标和最大下标值进行互换,0下标就是最大值,替换到最大下标,可以直接移除不需要移动数组
        swap(0, size - 1);
        // 数组元素减一
        size--;
        Priority e = array[size];
        array[size] = null; // heap GC
        // 然后进行维护大顶堆特点,父节点比子节点大,进行节点按照规则下层
        shiftDown(0);
        return (E) e;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return (E) array[0];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == array.length;
    }

    /**
     * 交换数组的2个下标的值
     * @param i 下标1
     * @param j 下标2
     */
    private void swap(int i, int j) {
        Priority temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    /**
     * 节点下层的方法,让其满足大顶堆的特点,父节点比子节点大.
     * @param parent 下层开始的数组下标, 我们这里一般是0下标开始比较
     */
    private void shiftDown(int parent) {
        // 找到parent节点的左右子节点
        int left = 2 * parent + 1;
        int right = left + 1;
        // 假设parent节点的值最大
        int max = parent;
        // 左右子节点谁大谁就替换parent节点
        if (left < size && array[left].priority() > array[max].priority()) {
            max = left;
        }
        if (right < size && array[right].priority() > array[max].priority()) {
            max = right;
        }
        // 左右子节点有比parent节点大的,就是进行数组的下标值互换,然后在进行递归比较.
        if (max != parent) {
            swap(max, parent);
            shiftDown(max);
        }
    }

    /**
     * 储存元素的数组
     */
    Priority[] array;
    /**
     * 队列元素的个数
     */
    private int size;

    /**
     * 构造器初始化底层储存数据的数组的容量
     * @param capacity 容量
     */
    public MaxHeapPriorityQueue(int capacity) {
        array = new Priority[capacity];
    }
}
